package com.okaixz.binarytree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 陈大专
 * @time 2025/8/6 8:26
 * @des
 **/
public class demo {
    public static void main(String[] args) {

        TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(7), new TreeNode(8))), new TreeNode(3));

//        boolean check = check(root.getLeft(), root.getRight());//是否对称
        invertTree(root);
        maxDeep(root);

        //        afterOrder(root);
        //递归深度优先遍历
        //        preIn(root);
        //        System.out.println();
        //        middleIn(root);
        //        System.out.println();
        //        afterIn(root);
    }
    public static void invertTree(TreeNode node){
        if (node == null) {
            return;
        }
        TreeNode left = node.getLeft();
        TreeNode right = node.getRight();
        node.setLeft(right);
        node.setRight(left);
        invertTree(left);
        invertTree(right);
    }

    public static int getMinDeep(TreeNode root){
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int minDeep=0;
        while (!queue.isEmpty()) {
            minDeep++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                System.out.print(node.getVal()+"\t");
                if (node.getLeft() != null) {
                    queue.offer(node.getLeft());
                }
                if (node.getRight() != null) {
                    queue.offer(node.getRight());
                }
                if(node.getLeft()==null&&node.getRight()==null){
                    return minDeep;
                }
            }
        }
        return minDeep;
    }

    public static int getDeep1(TreeNode node){
        if (node == null) {
            return 0;
        }
        int d1 = getDeep1(node.getLeft());
        int d2 = getDeep1(node.getRight());
        return Math.max(d1, d2) + 1;
    }
    public static int getDeep2(TreeNode node){
        if (node == null) {
            return 0;
        }
        TreeNode current = node;
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode prePop = null;
        int dp1=0;
        while (current != null || !stack.isEmpty()) {
            if (current != null) {
                stack.push(current);
                int size = stack.size();
                if(size>dp1){
                    dp1=size;
                }
                current = current.getLeft();
            } else {
                TreeNode pop = stack.peek();
                if (pop.getRight() == null) {
                    prePop = stack.pop();
                } else if (pop.getRight() == prePop) {
                    prePop = stack.pop();
                } else {
                    current = pop.getRight();
                }
            }
        }
        return dp1;
    }

    public static int maxDeep(TreeNode node){
        if (node == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        int deep=0;
        while (!queue.isEmpty()){
            int size=queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = queue.poll();
                System.out.print(treeNode.getVal()+"\t");
                if (treeNode.getLeft() != null) {
                    queue.offer(treeNode.getLeft());
                }
                if (treeNode.getRight() != null) {
                    queue.offer(treeNode.getRight());
                }
            }
            deep++;
            System.out.println();
        }
        return deep;

    }

    public static boolean check(TreeNode leftNode, TreeNode rightNode){
        if (leftNode == null && rightNode == null) {
            return true;
        }
        if(leftNode==null||rightNode==null){
            return false;
        }
        if(leftNode.getVal()!=rightNode.getVal()){
            return false;
        }
        return check(leftNode.getLeft(),rightNode.getRight())&&check(leftNode.getRight(),rightNode.getLeft());
    }


    public static void afterOrder(TreeNode node) {
        TreeNode current = node;
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode prePop = null;
        StringBuilder preSb=new StringBuilder("前序遍历：");
        StringBuilder middleSb=new StringBuilder("中序遍历：");
        StringBuilder postSb=new StringBuilder("后序遍历：");
        while (current != null || !stack.isEmpty()) {
            if (current != null) {
//                System.out.print(current.getVal()+"\t");
                preSb.append(current.getVal()+"\t");
                stack.push(current);
                current = current.getLeft();
            } else {
                TreeNode pop = stack.peek();
                if (pop.getRight() == null) {
                    postSb.append(pop.getVal()+"\t");
                    middleSb.append(pop.getVal()+"\t");
                    prePop = stack.pop();
                } else if (pop.getRight() == prePop) {
                    postSb.append(pop.getVal()+"\t");
                    prePop = stack.pop();
                } else {
                    middleSb.append(pop.getVal()+"\t");
                    current = pop.getRight();
                }
            }
        }
        System.out.println(preSb.toString());
        System.out.println(middleSb.toString());
        System.out.println(postSb.toString());
    }

    public static void preIn(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.getVal() + "\t");
        preIn(node.getLeft());
        preIn(node.getRight());
    }

    public static void middleIn(TreeNode node) {
        if (node == null) {
            return;
        }
        middleIn(node.getLeft());
        System.out.print(node.getVal() + "\t");
        middleIn(node.getRight());
    }

    public static void afterIn(TreeNode node) {
        if (node == null) {
            return;
        }
        afterIn(node.getLeft());
        afterIn(node.getRight());
        System.out.print(node.getVal() + "\t");
    }
}
